“Multicasting” is best described by distinguishing it from “unicasting” and “broadcasting”. A network typically comprises a plurality of nodes and a plurality of paths interconnecting the nodes. The network provides for data flow between nodes of the network. In most networks, each node is identified by an address, and data (generally in the form of a packet) destined for a particular node is “addressed” to that node. “Unicast data” refers to data destined for a single node and a “unicast address” refers to the address of that node. “Broadcast data” refers to data destined for all nodes in a network and broadcast addresses are special addresses reserved for broadcast data. Multicast data is data destined for a subset of nodes on the network using addresses reserved for multicasting. Unlike the nodes associated with unicast and broadcast addresses, the set of nodes associated with a multicast address may change dynamically, as nodes subscribe to and leave the multicast groups associated with multicast addresses.
The most widespread network today is the global internetwork of networks called the “Internet” (with a capitalized “I”). The Internet is a packet-based network, in that data sent to a destination node is bundled in packets, with each packet including a destination address, a source address, the data payload, and other fields, all according to the well-known Internet Protocol (“IP”). While the Internet is generally thought of as the global, publicly accessible network with which individuals, organizations, and business entities can connect to other individuals, organizations, and business entities around the world, the Internet Protocol is also used for networks that might be distinct from the Internet, such as an internal corporate network (“intranet”), a local area network (“LAN”), and other well-known variations of networks operating according to the Internet Protocol. Of course, many concepts that apply to IP networks may apply just as well to other types of networks. It should be understood that an IP network is used here as an example and not an exclusive example.
In an IP network, each node has an address, referred to as its “IP address”. In the current implementation, an IP address is four octets (i.e., four 8-bit values), but work is being done on moving to IPv6 (version 6), where IP addresses comprise sixteen octets. To send a packet from a sending node to a destination node, the sending node creates an IP packet according to the IP protocol, and according to that protocol, the packet contains the IP address of the sending node and the IP address of the destination node. In an IP network with a small number of nodes, a sender can send packets addressed with a broadcast IP address, but if that IP network is coupled to the Internet or other large network, broadcasting even one packet to the millions of nodes coupled to the Internet is impractical, wasteful and would probably result in the sender's node or network being isolated from the greater network.
Fortunately, the IP protocol provides a mechanism that achieves a result similar to broadcasting without a packet having to be received by millions of nodes that are uninterested in receiving the packet. The IP address space currently comprises 232, or 4,294,967,296, unique addresses (and IPv6 will comprise 2128 addresses). Some of these addresses are used for network control, while others are addresses of specific individual nodes (“unicast” addresses), while still others are referred to as “multicast” addresses. If a sender wants to send a packet to one particular destination node, the sender sets the destination address of the packet to the IP unicast address of that particular destination. However, if the sender wants to send a packet to many destinations, the sender can either send one distinct copy of the packet out for each of the destinations, with one copy of the packet being directed to each unicast address, or the sender can send a single copy of the packet to a multicast address. (The packet may later be copied as it is distributed across the network to the appropriate destinations; however, multicast is designed to make copies only when necessary, and hence is much more efficient.) We refer to the set of destinations associated with this multicast address as a multicast group. The multicast group does not need to be static over time; nodes may join or leave the multicast group. Joining is a process of indicating an interest in receiving packets that might be sent to that multicast group. In the simplest implementation, each multicast group has a multicast IP address and packets sent from a sender addressed to that multicast IP address are routed to nodes that have joined the multicast group.
One of the benefits of multicasting over broadcasting is that multicast packets do not need to be routed over branches of the network or paths that do not contain any nodes that are members of the multicast group. The multicasting process is far from simple, complicated by a number of factors, including the fact that multiple protocols must act in concert to deliver multicast packets to their destinations; there is no central location where the members of the multicasting group are listed and controlled; and evolving standards change multicasting requirements over time. Many difficulties of multicasting are well-known and documented so they need not be enumerated here.
In a conventional multicast environment, multicast protocols can be used to handle session management. With multicasting, an active multicast address must be associated with, or bound to, the set of nodes that are intended recipients of data transmitted over that address. Potential members of the group would typically use the IGMP (Internet Group Management Protocol) protocol to communicate with the last hop device to join and leave ongoing groups. Last hop devices are the last network devices along the path from the sender to hosts that fully support Internet Protocols (IP).
Because of the way IGMP joins and leaves are implemented (e.g., reception of join and leave messages by the last hop device is not guaranteed by the network), typically the last hop device has no reliable way to keep track of how many hosts are joined to a particular group, and therefore must poll the hosts to see if any are still joined to the group before stopping the flow of packets for the group. For example, if the last link is a point-to-point connection, then the last hop access device can immediately stop the flow as soon as it receives an IGMP leave, as it knows this comes from the only host along that interface. However, if the last link is a LAN, then there could be hundreds or even thousands of hosts beyond the link. In this case, polling to see which hosts are still attached is required and that polling can take several seconds to resolve, usually because the polling packets are not necessarily reliable.
To make the polling reliable, a series of three polls are made before stopping flow of the group, and each poll can take from one to three seconds in current implementations of last hop devices, leading to an aggregate leave reaction time of between three and nine seconds. In this time, even if all hosts have left the group and have no further interest in receiving multicast packets, the last hop device will continue to send the multicast data, until the last hop device is able to infer (from lack of response to the polling packets) that there are no group members left, resulting in much data being passed over the network without any node desiring that data. Thus, the slow leave latency of multicasting is a problem for networks that need to be used efficiently.
Overview of Layer-Based Multicast Content Delivery
Multicast layering enables the same content to be transmitted concurrently over multiple multicast sessions. One advantage to layering is that the transmission rates can vary widely over the different layers, which enables receivers with heterogeneous receive rates (modem, cable-modem, DSL, T1) to subscribe to the appropriate multicast group. In layer-based multicast transfers, the traffic destined for multicast groups is distributed among a plurality of layers. Having different layers with different send rates allows hosts with different receive rate capabilities to receive the multicast stream without stalling the network as a router waits for the slowest host to receive packets. Some solutions have been proposed to deal with layered multicasts. See, for example, L. Vicisano, et al., “TCP-like Congestion Control for Layered Multicast Data Transfer”, IEEE Infocom '98 (San Francisco, Calif., Mar. 28-Apr. 1, 1998).
Layered multicast congestion control affords the crucial ability to adjust one's receive rate dynamically based on network availability. Most instantiations of layered multicast allow receivers to accumulate layers, implying that a single receiver may subscribe to multiple layers simultaneously. The multicast layers associated with content are usually ordered consecutively from a lowest layer to a highest layer. A “cumulative layer” scheme is one where a receiver can only increase its reception rate by joining the lowest layer to which it is not currently joined and can only decrease its reception rate by leaving the highest layer to which it is currently joined. For example, suppose the rates of a six layer cumulative scheme are 10 Kbps (kilobits per second), 10 Kbps, 20 Kbps, 40 Kbps, 80 Kbps and 160 Kbps. A receiver may be joined to any consecutive set of these layers that includes the first layer. For example, a receiver may be joined to and receiving from the first three layers, at which point the reception rate is 40 Kbps. If the receiver wants to increase its rate at this point, it may do so only by joining the next layer, layer four, to increase its rate by 40 Kbps to 80 Kbps. If after this the receiver wishes to decrease its rate, it may do so only by leaving the top layer, layer four, to decrease its rate by 40 Kbps from 80 Kbps down to 40 Kbps. Thus, the number of different rates that a receiver can receive at using a cumulative scheme is limited to the number of different layers in the scheme.
A “relaxed layer” scheme is a generalization of a cumulative layer scheme, wherein receivers are allowed to join and leave arbitrary layers. A relaxed layer scheme may offer advantages over a cumulative layer scheme, such as more fine-grained control over the possible reception rates. Specifically, in a cumulative layer scheme, there are generally fewer possibilities for the reception rates than in a relaxed layer scheme with the same number of layers. Hence in a relaxed layer scheme a receiver can tune their reception rate more exactly to its needs. For example, suppose the rates of a six layer scheme are 10 Kbps, 20 Kbps, 40 Kbps, 70 Kbps, 120 Kbps, and 200 Kbps, respectively. Suppose further that a receiver is currently joined to and receiving the first three layers, so the aggregate reception rate of that receiver is currently 70 Kbps. If the receiver wants to increase its rate by 10 Kbps, it can achieve this with a relaxed scheme by leaving the second and third layers and joining the fourth layer, thus increasing its reception rate by 70 Kbps-40 Kbps-20 Kbps=10 Kbps. By carefully choosing the rates of the different layers, with a relaxed scheme the receiver can receive at many more rates than the number of different layers, and thus exercise much finer grain control over the aggregate reception rate. This is a key advantage of a relaxed scheme over a cumulative scheme.
From the above example of a relaxed scheme, it is evident that the rates on the different layers can be designed so that the difference between consecutive achievable reception rates is always the same small amount x (x=10 Kbps in the example above), and so that the number of joins and leaves needed to increase the reception rate by x is a small constant. For example, the six layer relaxed scheme described above can be generalized so that the rate of the first layer is x, the rate of the second layer is x, and in general, the rate of the i-th layer is equal to the sum of the rates of layers i−1 and i−2 plus x. Then, to increase the reception rate by x, the receiver joins the smallest layer not currently joined and leaves the two previous layers (if they both exist).
A disadvantage of a relaxed scheme versus a cumulative scheme is that it is harder with the relaxed scheme compared to the cumulative scheme to synchronize all receivers behind a bottleneck link to be joined to exactly the same set of layers. This is an issue because it means that although all the flow from the layers going through the bottleneck link is of use to all the receivers behind the bottleneck link, not all of them are receiving all of this flow if they are joined to different subsets of the layers.
An issue with both layered schemes is that data put into the different layers must be carefully orchestrated to'ensure that receivers can in fact recover all of the transmitted content, preferably without receiving duplicated data. In practice, this can be very difficult to achieve. In the setting of reliable content distribution, the layering mechanisms and congestion control techniques described in U.S. Pat. No. 6,307,487 (application Ser. No. 09/246,015, entitled “Information Additive Code Generator And Decoder For Communication Systems” and filed Feb. 5, 1999) (hereinafter “Luby I”) and U.S. Pat. No. 6,320,520 (application Ser. No. 09/399,201, entitled “Information Additive Group Code Generator And Decoder For Communication Systems” and filed Sep. 17, 1999) (hereinafter “Luby II”), each of which is incorporated by reference herein for all purposes, might be used to accomplish reliable content distribution with negligible overhead in terms of duplicated data.
Even with careful orchestration, the slowness of leave requests induces significant wasted traffic in layered multicast schemes. A receiver may wish to leave a layer, either when the receiver has received all of the relevant data from that layer or, more commonly, when lowering the receive rate is in response to dynamically changing network congestion conditions. The leave operation is meant to signal that the receiver no longer desires packets for the corresponding layer. Because leave times have high latency, packets may continue to be sent to the receiver over that layer long after the leave request is initiated and until the leave request is fully processed. These packets may be wasted, in that there may be no downstream node that requires or desires these packets, but they are sent and consume network resources. Indeed, these wasted packets may have a severe impact on network performance, if the leave was initiated in response to network congestion.